typedef struct SBTNode{
	ElemType val;
	int size;
	struct SBTNode *lchild, *rchild;
}SBTNode, *SBTree;
//Right Rotate
void RightRotate(SBTree &T){
	if (T->lchild){
		SBTNode *p = T->lchild;
		T->lchild = p->rchild; p->rchild = T;
		p->size = T->size; T->size = T->lchild->size + T->rchild->size + 1;
		T = p;
	}
}
//LeftRotate
void LeftRotate(SBTree &T){
	if (T->rchild){
		SBTNode *p = T->rchild;
		T->rchild = p->lchild; p->lchild = T;
		p->size = T->size; T->size = T->lchild->size + T->rchild->size + 1;
		T = p;
	}
}
//Maintain
void Maintain(SBTree &T, bool rightdeeper){
	if (!rightdeeper){
		if (T->lchild->lchild->size > T-rchild->size){
			RightRotate(T);
		}
		else {
			LeftRotate(T->lchild); RightRotate(T);
		}
	}
	else {
		if (T->rchild->rchild->size > T->lchild->size){
			LeftRotate(T);
		}
		else {
			RightRotate(T->rchild); LeftRotate(T);
		}
	}
	Maintain(T->rchild, true);
	Maintain(T->lchild, false);
	Maintain(T, false); Maintain(T, true);
}
//Insert
void InsertSizeBalancedTree(SBTree &T, ElemType key){
	if (!T){
		T = (SBTree)malloc(sizeof(SBTNode));
		T->val = key; T->size = 1;
		T->lchild = T->rchild = NULL;
		return;
	}
	++T->size;
	if (key > T->val){
		InsertSizeBalancedTree(T->rchild, key);
		Maintain(T, true);
	}
	else {
		InsertSizeBalancedTree(T->lchild, key);
		Maintain(T, false)
	}
}
//Delete
SBTree DeleteSizeBalancedTree(SBTree &T, ElemType key){
	if (!T) return;
	SBTree record;
	if (T->size <= 2){
		record = T;
		T = T->lchild ? T->lchild : T->rchild;
		record->lchild = record->rchild = NULL;
		return record;
	}
	--T->size;
	if (T->val == key){
		record = DeleteSizeBalancedTree(T->lchild, key + 1);
		T->val = record->val;
		Maintain(T, true);
	}
	else if (T->val > key){
		record = DeleteSizeBalancedTree(T->lchild, key);
		Maintain(T, true);
	}
	else {
		record = DeleteSizeBalancedTree(T->rchild, key);
		Maintain(T, false);
	}
	return record;
}
//Recursion Search
SBTree RecursionSearchSizeBalancedTree(SBTree T, int key){
	if (!T) return NULL;
	if (T->val == key){
		return T;
	}
	else if (T->val > key){
		return SearchSizeBalancedTree(T->lchild, key);
	}
	else return SearchSizeBalancedTree(T->rchild, key);
}
//Unrecursion Search
SBTree UnrecursionSearchSizeBalancedTree(SBTree T, int key){
	SBTree p = T;
	while (p && p->val != key){
		if (p->val > key){
			if (p->lchild){
				p = p->lchild;
			}
			else break;
		}
		else {
			if (p->rchild){
				p = p->rchild;
			}
			else break;
		}
	}
	return p;
}
SBTree PredecessorSizeBalancedTree(SBTree T, int key){
	SBTree p = UnrecursionSearchSizeBalancedTree(T, key);
	if (p && p->val == key){
		return UnrecursionSearchSizeBalancedTree(p->lchild, key + 1);
	}
	return NULL;
}

SBTree SuccessorSizeBalancedTree(SBTree T, int key){
	SBTree p = UnrecursionSearchSizeBalancedTree(T, key);
	if (p && p->val == key){
		return UnrecursionSearchSizeBalancedTree(p->rchlid, key - 1);
	}
	return NULL;
}

int RankSizeBalancedTree(SBTree T, int key){
	if (T){
		if (T->val == key){
			return T->lchild ? (T->lchild->size + 1) : 1;
		}
		else if (T->val > key){
			return RankSizeBalancedTree(T->lchild, key);
		}
		else {
			int rankt = T->lchild ? (T->lchild->size + 1) : 1;
			return RankSizeBalancedTree(T->rchild, key) + rankt;
		}
	}
	else return 0;
}
//find the rank k key in the size balanced tree, need T != NULL && k > 0 && k <= T->size
SBTree FindKthSizeBalancedTree(SBTree T, int k){
	int rankt = T->lchild ? (T->lchild->size + 1) : 1;
	if (rankt == k){
		return T;
	}
	else if (rankt < k){
		return FindKthSizeBalancedTree(T->rchild, k - rankt);
	}
	else return FindKthSizeBalancedTree(T->lchild, k);
}

SBTree FindMaxSizeBalancedTree(SBTree T){
	if (T){
		return FindKthSizeBalancedTree(T, T->size);
	}
	else return NULL;
}

SBTree FindMinSizeBalancedTree(SBTree T){
	if (T){
		return FindKthSizeBalancedTree(T, 1);
	}
	else return NULL;
}